/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pagrafo.genetico;

import java.util.Arrays;
import pagrafo.grafo.Grafo;

/**
 *
 * @author Fabricio
 */
public class CrossoverAlternado {
    
    /**
     * Recebe 2 cromossomos pais e retorna um vetor de 2 posições contendo os cromossomos filhos
     * @param a
     * @param b
     * @return 
     */
    private static int[][] crossover(Cromossomo a, Cromossomo b, int n, int k) {

        //Vetores dos pais:
        int[] paiA = a.v.clone();
        int[] paiB = b.v.clone();

        //Para teste
//        System.out.print("Pai A: ");
//        for (int i = 0; i < paiA.length; i++) {
//            System.out.print(paiA[i]);
//            System.out.print(",");
//        }
//        System.out.println("");
//        System.out.print("Pai B: ");
//        for (int i = 0; i < paiB.length; i++) {
//            System.out.print(paiB[i]);
//            System.out.print(",");
//        }
//        System.out.println("");

        //Clona os pais para os filhos
        int[] filhoA = paiB.clone();
        int[] filhoB = paiA.clone();

        //mantém apenas os 0s nos filhos, todos os outros são marcados -1
        for (int i = 0; i < filhoA.length; i++) {
            if (paiA[i] != 0) {
                filhoA[i] = -1;
            } else {
                filhoA[i] = 0;
            }
            if (paiB[i] != 0) {
                filhoB[i] = -1;
            } else {
                filhoB[i] = 0;
            }
        }

        //Ponteiros de controle para a alternância dos genes dos pais
        int pA = 0;
        int pB = 0;

        //Variável alternante que controla qual dos pais será utilizado
        boolean pegarA = true;

        //Variaveis de controle dos vertices já preenchidos nos filhos
        boolean[] cA = new boolean[n+k];
        //boolean[] cA = new boolean[7];
        Arrays.fill(cA, Boolean.FALSE);
        cA[0] = true;
        boolean[] cB = new boolean[n+k];
        //boolean[] cB = new boolean[7];
        Arrays.fill(cB, Boolean.FALSE);
        cB[0] = true;

        //Preenche o filhoA
        for (int i = 1; i < filhoA.length - 1; i++) {

            //Caso seja zero nõa faz nada
            if (filhoA[i] == 0) {
                continue;
            }

            if (pegarA) {
                //Pega o próximo gene
                pA = getProximoGene(pA, paiA, cA);
                //Testa
                if (pA == -1) {
                    continue;
                }
                //Posiciona o gene no filho
                filhoA[i] = paiA[pA];
                cA[paiA[pA]] = true;
                //Apaga o gene na cópia do pai
                paiA[pA] = -1;
                //Alterna entre o pai
                pegarA = !pegarA;
            } else {
                //Pega o próximo gene
                pB = getProximoGene(pB, paiB, cA);
                //Testa
                if (pB == -1) {
                    continue;
                }
                //Posiciona o gene no filho
                filhoA[i] = paiB[pB];
                cA[paiB[pB]] = true;
                //Apaga o gene na cópia do pai
                paiB[pB] = -1;
                //Alterna entre o pai
                pegarA = !pegarA;
            }
        }

        //Reseta variáveis
        pA = 0;
        pB = 0;
        pegarA = false;

        //Preenche o filhoB
        for (int i = 1; i < filhoB.length - 1; i++) {

            //Caso seja zero nõa faz nada
            if (filhoB[i] == 0) {
                continue;
            }

            if (pegarA) {
                //Pega o próximo gene
                pA = getProximoGene(pA, paiA, cB);
                //Testa
                if (pA == -1) {
                    continue;
                }
                //Posiciona o gene no filho
                filhoB[i] = paiA[pA];
                cB[paiA[pA]] = true;
                //Apaga o gene na cópia do pai
                paiA[pA] = -1;
                //Alterna entre o pai
                pegarA = !pegarA;
            } else {
                //Pega o próximo gene
                pB = getProximoGene(pB, paiB, cB);
                //Testa
                if (pB == -1) {
                    continue;
                }
                //Posiciona o gene no filho
                filhoB[i] = paiB[pB];
                cB[paiB[pB]] = true;
                //Apaga o gene na cópia do pai
                paiB[pB] = -1;
                //Alterna entre o pai
                pegarA = !pegarA;
            }
        }
        
        //Para Teste
//        System.out.print("Filho A: ");
//        for (int i = 0; i < filhoA.length; i++) {
//            System.out.print(filhoA[i] + ",");
//        }
//        System.out.println("");
//        System.out.print("Filho B: ");
//        for (int i = 0; i < filhoB.length; i++) {
//            System.out.print(filhoB[i] + ",");
//        }
//        System.out.println("");

        int[][] par = new int[][]{filhoA,filhoB};

        return par;
    }
    
    private static int getProximoGene(int p, int[] v, boolean[] usado) {
        for (int i = 0; i < v.length; i++) {
            p++;

            //Retorna ao inicio caso tenha chegado ao fim do vetor
            if (p == v.length) {
                p = 1;
            }

            //Caso seja diferente de 0 e -1 e o valor não tenha sido utilizado retorna a posição
            if (v[p] != 0 && v[p] != -1 && !usado[v[p]]) {
                return p;
            }
        }
        //Caso todas as posições do vetor já estejam com 0 ou -1
        return -1;
    }
    
    public static Cromossomo[] executar(Cromossomo paiA, Cromossomo paiB, Grafo g, int k, double capacidade){
        int[][] filhosv = crossover(paiA, paiB, g.sizeVertices(), k);
        Cromossomo[] cromossomos = new Cromossomo[2];
        cromossomos[0] = new Cromossomo(g, k, capacidade, filhosv[0]);
        cromossomos[1] = new Cromossomo(g, k, capacidade, filhosv[1]);      
        return cromossomos;
    }
}
